package personal.leil.learning.dijkstra;

import personal.leil.learning.undigraph.EdgeUndirected;
import personal.leil.learning.undigraph.Undigraph;
import personal.leil.learning.undigraph.Vertex;

import java.util.*;

/**
 * Dijkstra算法是一种用于求解单源最短路径的贪心算法
 * <p>
 * 以下是Dijkstra算法的基本思路：
 *     <ol>
 *         <li>初始化： 创建一个距离数组distance，用于存储源点到每个顶点的当前最短路径长度。初始时，将源点的距离设为0，其他顶点的距离设为无穷大</li>
 *         <li>选择最短路径： 从未访问的顶点中选择距离最短的顶点作为当前顶点，将其标记为已访问</li>
 *         <li>更新距离： 对于当前顶点的所有邻居，更新其距离数组中的距离。如果通过当前顶点可以获得更短的路径，则更新距离数组</li>
 *         <li>重复步骤2和3： 重复选择最短路径和更新距离的步骤，直到所有顶点都被访问</li>
 *         <li>最终结果： 最终distance数组中存储的就是源点到每个顶点的最短路径长度</li>
 *     </ol>
 * </p>
 *
 * @author Leil
 * @version 1.0
 * @since 2024/1/23
 */
public class Dijkstra {

    public static Map<Vertex, Integer> findMinimumDistance(Vertex source) {
        Map<Vertex, Integer> distanceMap = new HashMap<>();
        distanceMap.put(source, 0);
        recursion(source, distanceMap);
        return distanceMap;
    }


    /**
     * 递归的找到每个节点到source的最小距离
     * @param source        每次递归的源节点
     * @param distanceMap   节点到源节点的距离
     */
    public static void recursion(Vertex source,
                                 Map<Vertex, Integer> distanceMap) {
        if (!distanceMap.containsKey(source)) {
            return;
        }
        Integer distanceFromSource = distanceMap.get(source);
        HashSet<EdgeUndirected> edges = source.edges;
        for (EdgeUndirected edge : edges) {
            Vertex another = edge.findAnother(source);
            Integer distanceFromTarget = distanceMap.get(another);
            if (distanceFromTarget == null
                    || (distanceFromTarget > distanceFromSource + edge.weight)) {
                distanceMap.put(another, distanceFromSource + edge.weight);
                recursion(another, distanceMap);
            }
        }
    }


    /************************* For Test *************************/
    public static void main(String[] args) {
        Undigraph graph = new Undigraph();
        Vertex v1 = new Vertex(1);
        graph.addVertex(v1);
        Vertex v2 = new Vertex(2);
        graph.addVertex(v2);
        Vertex v3 = new Vertex(3);
        graph.addVertex(v3);
        Vertex v4 = new Vertex(4);
        graph.addVertex(v4);
        Vertex v5 = new Vertex(5);
        graph.addVertex(v5);

        v1.addNeighbor(v2);
        graph.addEdge(new EdgeUndirected(v1, v2, 3));
        v1.addNeighbor(v3);
        graph.addEdge(new EdgeUndirected(v1, v3, 15));
        v1.addNeighbor(v4);
        graph.addEdge(new EdgeUndirected(v1, v4, 9));
        v3.addNeighbor(v4);
        graph.addEdge(new EdgeUndirected(v3, v4, 7));
        v2.addNeighbor(v3);
        graph.addEdge(new EdgeUndirected(v2, v3, 2));
        v2.addNeighbor(v5);
        graph.addEdge(new EdgeUndirected(v2, v5, 200));
        v3.addNeighbor(v5);
        graph.addEdge(new EdgeUndirected(v3, v5, 14));
        v4.addNeighbor(v5);
        graph.addEdge(new EdgeUndirected(v4, v5, 16));

        Map<Vertex, Integer> distances = findMinimumDistance(v1);
        for (Map.Entry<Vertex, Integer> entry : distances.entrySet()) {
            System.out.println(entry.getKey() + "===" + entry.getValue());
        }
    }


}
